package com.wwz.leetcode;

import com.wwz.common.ListNode;
import org.junit.Test;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */
public class LeetCode23_1 {

    @Test
    public void test() {
        // [1,4,5],[1,3,4],[2,6]
        ListNode listNode3 = new ListNode(5, null);
        ListNode listNode2 = new ListNode(4, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);

        ListNode listNode23 = new ListNode(4, null);
        ListNode listNode22 = new ListNode(3, listNode23);
        ListNode listNode21 = new ListNode(1, listNode22);


        ListNode listNode32 = new ListNode(6, null);
        ListNode listNode31 = new ListNode(2, listNode32);
        ListNode[] lists = {listNode1, listNode21,listNode31};

//        ListNode listNode2 = null;
//        ListNode listNode1 = new ListNode(1, null);
//        ListNode[] lists = {listNode1, listNode2};
        ListNode res = mergeKLists(lists);
        while (res != null) {
            System.out.println(res.val);
            res = res.next;
        }

    }


    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        if (lists.length < 2) {
            return lists[0];
        }
        ListNode listNode = mergeTwoLists(lists[0], lists[1]);
        // 循环合并两个有序链表
        for (int i = 2; i < lists.length; i++) {
            listNode = mergeTwoLists(listNode, lists[i]);
        }
        return listNode;
    }

    public ListNode mergeTwoLists(ListNode listNode1, ListNode listNode2) {
        ListNode resNode = new ListNode();
        ListNode cur = resNode;
        while (listNode1 != null && listNode2 != null) {
            if (listNode1.val > listNode2.val) {
                cur.next = listNode2;
                cur = listNode2;
                listNode2 = listNode2.next;
            } else {
                cur.next = listNode1;
                cur = listNode1;
                listNode1 = listNode1.next;
            }

        }
        if (listNode1 == null) {
            cur.next = listNode2;
        }
        if (listNode2 == null) {
            cur.next = listNode1;
        }
        return resNode.next;

    }
}
